﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace PacCraft
{
    class Link
    {
        public double cost;
        public Node to;

        public Link(ref Node _to, double _cost)
        {
            this.cost = _cost;
            to = _to;
        }
    }

    class Node
    {
        public int x, y;
        private List<Link> links = new List<Link>();

        // for the search
        public double cost;
        public Node previous;
        public double estimatedCost;

        public Node(int _x, int _y)
        {
            x = _x;
            y = _y;
        }

        public void createLink(Node to, double cost)
        {
            Link newLink = new Link(ref to, cost);
            links.Add(newLink);
        }

        public List<Link> getLinks()
        {
            return links;
        }

        public Vector2 getPosition()
        {
            return new Vector2(x, y);
        }

        public override string ToString()
        {
            string retour = "Node [" + x + ", " + y + "]" + '\n';
            foreach (Link node in links)
                retour += "-> Linked to [" + node.to.x + ", " + node.to.y + "] (Cost : " + node.cost + ")" + '\n';
            retour += '\n';
            return retour;
        }
    }

    class Graph
    {
        List<Node> nodes = new List<Node>();

        public Graph()
        {
        }

        public Graph(Map map)
        {
            for (int i = 1; i < map.map.Length - 1; ++i)
            {
                for (int j = 1; j < map.map[i].Length - 1; ++j)
                {
                    if (map.map[i][j] != '1')
                    {
                        createNode(i, j);
                        if (map.map[i + 1][j] != '1')
                            createLink(new Vector2(i, j), new Vector2(i + 1, j), 1);
                        if (map.map[i - 1][j] != '1')
                            createLink(new Vector2(i, j), new Vector2(i - 1, j), 1);
                        if (map.map[i][j + 1] != '1')
                            createLink(new Vector2(i, j), new Vector2(i, j + 1), 1);
                        if (map.map[i][j - 1] != '1')
                            createLink(new Vector2(i, j), new Vector2(i, j - 1), 1);
                    }
                }
            }
            clearGraph();
        }

        public Node createNode(int x, int y)
        {
            if (isNode(x, y))
                return getNode(x, y);

            Node newNode = new Node(x, y);
            nodes.Add(newNode);
            return newNode;
        }

        public void createLink(Node from, Node to, double cost)
        {
            from.createLink(to, cost);
            to.createLink(from, cost);
        }

        public void createLink(Vector2 from, Vector2 to, double cost)
        {
            Node nodeFrom = getNode((int)from.X, (int)from.Y);
            Node nodeTo = getNode((int)to.X, (int)to.Y);
            nodeFrom.createLink(nodeTo, cost);
            nodeTo.createLink(nodeFrom, cost);
        }

        public Node getNode(int x, int y)
        {
            if (isNode(x, y))
            {
                foreach (Node node in nodes)
                    if (node.x == x && node.y == y)
                        return node;
            }
            // else
                return createNode(x, y);
        }

        public List<Node> getNodes()
        {
            return nodes;
        }

        public List<Node> getPath(Vector2 from, Vector2 to)
        {
            Node fromNode = getNode((int)from.X, (int)from.Y);
            Node toNode = getNode((int)to.X, (int)to.Y);
            return getPath(fromNode, toNode);
        }

        public List<Node> getPath(Node from, Node to)
        {
            List<Node> path = new List<Node>();
            List<Node> pile = new List<Node>();

            foreach (Node node in nodes)
            {
                node.cost = (node == from)?(0):(2000000);
                node.previous = null;
                pile.Add(node);
            }

            Node current = from;
            while (pile.Count() != 0)
            {
                double min = 2000000;
                foreach (Node node in pile)
                {
                    if (node.cost <= min)
                    {
                        min = node.cost;
                        current = node;
                    }
                }

                List<Link> childrens = current.getLinks();
                foreach (Link child in childrens)
                {
                    if (current.cost + child.cost < child.to.cost)
                    {
                        
                        child.to.cost = current.cost + child.cost;
                        child.to.previous = current;
                    }
                }
                pile.Remove(current);
            }

            current = to;
            while (current.previous != null)
            {
                path.Add(current);
                current = current.previous;
            }
            path.Add(from);
            path.Reverse();
            return path;
        }

        public bool isNode(int x, int y)
        {
            foreach (Node node in nodes)
            {
                if (node.x == x && node.y == y)
                    return true;
            }
            return false;
        }

        public override string ToString()
        {
            string retour = "";

            foreach (Node node in nodes)
                retour += node.ToString();
            return retour;
        }

        private void clearGraph()
        {
            /*
             * foreach (Node node in nodes)
            {
                if (node.getLinks().Count == 0)
                    nodes.Remove(node);
            }
             */
        }

        private int countAround(int x, int y, ref Map map)
        {
            int retour = 0;
            if (map.map[x + 1][y] == '1')
                ++retour;
            if (map.map[x - 1][y] == '1')
                ++retour;
            if (map.map[x][y + 1] == '1')
                ++retour;
            if (map.map[x][y - 1] == '1')
                ++retour;
            return retour;
        }
    }
}
